The present disclosure relates to representation and retrieval of data structures in databases.
Traditionally, stored knowledge has often been represented in a directed acyclic graph (DAG) structure called a semantic network, and more recently, a knowledge ontology. For large knowledge structures, a DAG structure (typically hierarchical) is frequently used for structuring ontology nodes: edges connect more general (source) nodes to more specific (destination) nodes. This DAG structure is often created and stored in a database.
A traditional method for representing trees and DAGs in a database involves the use of Adjacency Lists. An Adjacency List typically consists of pairs of nodes, each pair representing a parent-child connection between nodes. Adjacency Lists typically require navigation of the stored DAG structure and are frequently inefficient for larger graphs. Insertions, updates, and deletions are relatively efficient, however, traversing large portions of a ontology knowledge structure stored using Adjacency Lists can be inefficient.
Recent optimizations include recording full tree paths or using so-called nested-sets and nested intervals to allow sub trees to be efficiently and quickly retrieved. Such methods are generally restricted to strict tree structures. The use of Materialized Paths is also a known approach for representing and searching tree data structures in a database. Other techniques include fractional methods, such as Farey Fractions and Continued Fractions, and simple path enumeration approaches for tree structures.